package bintree.leetcode;

/**
 * @author yuisama
 * @date 2022/05/12 21:11
 **/
public class Num572_IsSubTree {
    /**
     * 传入两颗树root和subRoot就能判断root是否包含subRoot
     * @param root
     * @param subRoot
     * @return
     */
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        // 边界
        if (root == null && subRoot == null) {
            return true;
        }
        if (root == null || subRoot == null) {
            return false;
        }
        // 恰好root和subRoot就是相同的树 => true
        return isSameTree(root,subRoot) || isSubtree(root.left,subRoot) || isSubtree(root.right,subRoot);
    }

    public boolean isSameTree(TreeNode p, TreeNode q) {
        // 1.边界
        if (p == null && q == null) {
            // 都是空树，就认为相同
            return true;
        }
        if (p == null || q == null) {
            // 有一棵树为空，另一棵树不为空
            return false;
        }
        // p和q都不为空，判断一下节点值。子树的判断交给子函数
        return p.val == q.val && isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
    }
}